package th.retrofit.lib;

import java.util.Deque;
import java.util.LinkedList;


/**
 * https://leetcode-cn.com/problems/jump-game-ii/
 * 给你一个非负整数数组nums ，你最初位于数组的第一个位置。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 * 假设你总是可以到达数组的最后一个位置
 */
public class Solution45 {

    public int jump(int[] nums) {
        int step = 0;
        int nLen = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        deque.offer(0);
        while (!deque.isEmpty()) {
            step++;
            int size = deque.size();
            for (int j = 0; j < size; j++) {
                int index = deque.poll();
                for (int i = 1; i <= nums[index]; i++) {
                    int newIndex = index + i;
                    if (newIndex == nLen - 1) {
                        return step;
                    } else if (index + i < nLen) {
                        deque.offer(index + i);
                    } else {
                        break;
                    }
                }
            }
        }
        return 0;
    }

    public int jump1(int[] nums) {
        int steps = 0;
        int end = 0;
        int maxPos = 0;
        int nLen = nums.length - 1;
        for (int i = 0; i < nLen; i++) {
            maxPos = Math.max(maxPos, i + nums[i]);
            if (i == end) {
                end = maxPos;
                steps++;
            }
        }
        return steps;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{8,2,4,4,4,9,5,2,5,8,8,0,8,6,9,1,1,6,3,5,1,2,6,6,0,4,8,6,0,3,2,8,7,6,5,1,7,0,3,4,8,3,5,9,0,4,0,1,0,5,9,2,0,7,0,2,1,0,8,2,5,1,2,3,9,7,4,7,0,0,1,8,5,6,7,5,1,9,9,3,5,0,7,5};
        System.out.println(new Solution45().jump1(nums));
    }

}
